class Room:
    name = ""
    numOfSeats = 0
    occupiedSeats = 0
    seatedPersons = []

    def __init__(self, name, seats):
        self.name = name
        self.numOfSeats = seats
        self.occupiedSeats = 0
        self.seatedPersons = []

    def Print( self ):
        print( self.name, "seats:", self.numOfSeats )

class Person:
    name = None
    smoker = False
    manyVisitors = False
    status = 0
    room = None

    def __init__(self, name, smoking, visitors, status ):
        self.name = name
        self.smoker = smoking
        self.manyVisitors = visitors
        self.status = status

    def Print( self ):
        print( self.name, self.smoker, self.manyVisitors, self.status )

class ConstraintSatisfactionProblem:
    Persons = []
    UnAssigned = []
    Rooms = []
    Constraints = []

    def __init__(self):
        self.Persons = []
        self.UnAssigned = []
        self.Rooms = []
        self.Constraints = [ ]
        self.LoadConstraints()

    def RoomFull( self, person, room ):
        violated = False
        if room.occupiedSeats >= room.numOfSeats:
            violated = True
        return violated

    def HighStatusInLargeOffice( self, person, room ):
        violated = False
        if person.status < 3:
            if room.numOfSeats < 2:
                violated = True
        return violated

    def HeadAndProfessor( self, person, room ):
        violated = False

        if person.status < 3:
            if room.occupiedSeats != 0:
                violated = True

        return violated

    def NonSmokerAndSmoker( self, person, room ):
        violated = False

        if person.smoker:
            for otherPerson in room.seatedPersons:
                if not otherPerson.smoker:
                    return True
        elif not person.smoker:
            for otherPerson in room.seatedPersons:
                if otherPerson.smoker:
                    return True

        return violated

    def ManyVisitorsAndFewVisitors( self, person, room ):
        violated = False

        if person.manyVisitors:
            for otherPerson in room.seatedPersons:
                if otherPerson.manyVisitors:
                    violated = True

        return violated

    def LoadConstraints( self ):
        self.Constraints.append( self.RoomFull )
        self.Constraints.append( self.HighStatusInLargeOffice )
        self.Constraints.append( self.HeadAndProfessor )
        self.Constraints.append( self.NonSmokerAndSmoker )
        self.Constraints.append( self.ManyVisitorsAndFewVisitors )








########### MAIN: ############

def RoomList( person, assignment, csp ):
    roomsToReturn = []

    for room in csp.Rooms:
        violated = False
        for func in csp.Constraints:
            if func( person, room ):
                violated = True
        if not violated:
            roomsToReturn.append(room)

    return roomsToReturn

def Assign( person, room, assignment ):
    assignment[person] = room
    room.seatedPersons.append( person )
    room.occupiedSeats += 1

def UnAssign( person, room, assignment ):
    del assignment[person]
    room.seatedPersons.remove( person )
    room.occupiedSeats -= 1


def RecursiveBacktrack( csp, assignment ):
    if csp.Persons == []:
        return assignment
    person = csp.Persons.pop()
    for room in RoomList( person, assignment, csp ):
        Assign( person, room, assignment )
        result = RecursiveBacktrack( csp, assignment )
        if result != None:
            return result
        UnAssign( person, room, assignment )
    csp.Persons.insert(0, person )

    if len( csp.Persons ) < len( csp.UnAssigned ):
        csp.UnAssigned = list( csp.Persons )

    return None


# Implement the heuristics of mostConstrainedVariable and LeastConstrainingValue below
def RecursiveBacktrackWithHeuristics( csp, assignment ):
    if csp.Persons == []:
        return assignment
    person = csp.Persons.pop()
    for room in RoomList( person, assignment, csp ):
        Assign( person, room, assignment )
        result = RecursiveBacktrack( csp, assignment )
        if result != None:
            return result
        UnAssign( person, room, assignment )
    csp.Persons.insert(0, person )

    if len( csp.Persons ) < len( csp.UnAssigned ):
        csp.UnAssigned = list( csp.Persons )

    return None

def AssignAllPersons( csp ):
    assignment = {}
    return RecursiveBacktrack( csp, assignment )


csp = ConstraintSatisfactionProblem()




csp.Rooms.append( Room('T13', 1) )
csp.Rooms.append( Room('T14', 1) )
csp.Rooms.append( Room('T15', 1) )
csp.Rooms.append( Room('T16', 1) )
csp.Rooms.append( Room('T11', 2) )
csp.Rooms.append( Room('T12', 2) )
csp.Rooms.append( Room('T10', 3) )
# Uncomment row below to make the problem solvable. 
#csp.Rooms.append( Room('T09', 2) )

csp.Persons.append( Person('A', False, True, 1) )
csp.Persons.append( Person('B', False, True, 2) )
csp.Persons.append( Person('C', False, False, 2) )
csp.Persons.append( Person('D', True, True, 2) )
csp.Persons.append( Person('E', True, True, 3) )
csp.Persons.append( Person('F', False, False, 3) )
csp.Persons.append( Person('G', False, False, 3) )
csp.Persons.append( Person('H', False, True, 4) )
csp.Persons.append( Person('I', True, False, 4) )
csp.Persons.append( Person('J', True, False, 4) )
csp.Persons.append( Person('K', False, False, 4) )

csp.UnAssigned = list( csp.Persons )


result = AssignAllPersons( csp )

if result != None:
    for k in result:
        print( k.name, k.smoker, k.manyVisitors, k.status, "is in", result[k].name )
else:
    for p in csp.UnAssigned:
        print( p.name, p.smoker, p.manyVisitors, p.status, "Got no room" )